# -*- coding: utf-8 -*-
# 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合
# 例如，给出 n = 3，生成结果为：
# [
#   "((()))",
#   "(()())",
#   "(())()",
#   "()(())",
#   "()()()"
# ]

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n <=0:
            return [];

        rtn = {"()" : 1};
        for i in xrange(1, n):
            keys = rtn.keys();
            for key in keys:
                for j in xrange(0, len(key)):
                    rtn[ key[0:j] + "()" + key[j:len(key)] ] = 1;
                del rtn[key];
        return rtn.keys();

t = Solution();
print t.generateParenthesis(3);